ECE 6605 - Information Theory

Prof. Matthieu Bloch

Thursday, September 28, 2023

Announcements

  • Assignment 2
    • Posted on Canvas/Gradescope on Monday, September 18, 2023
    • Due today (hard deadline on Saturday September 30, 2023)
    • 6 problems on chain rules, typicality
    • Read Chapter 4 of Thomas M. Cover and Joy A. Thomas, Elements of Information Theory
    • Use Piazza for questions and watch office hour video recording
  • Assignment 1
    • Trying to submit grades by tomorrow
  • Last time
    • Applications of one-shot result for achievability of source coding
    • Second order asymptotics of source coding
  • Today
    • A cool new result: Source coding with side information
    • Privacy amplification

Source coding with side information

Image
Fixed-length source coding with side information model

A \((n,M_n)\) code for source coding a discrete memoryless source \(p_X\) with side information \(Y\) consists of:

  1. A encoding function \(f_n:\calX^n\to\set{1;M_n}\)
  2. A decoding function \(g_n:\set{1;M_n}\times\calY^n\to \calX^n\)
  • The performance of an \((n,M_n)\) code is measured in terms of

    1. The rate of the code \(R\eqdef \frac{\log_2 M_n}{n}\) (bits/source symbol)

    2. The average probability of error

      \[\begin{align*} P_e^{(n)}(\calC) \eqdef \P{\widehat{X}^n\neq X^n} \eqdef \sum_{(x^n,y^n)\in\calX^n\times\calY^n}P_{XY}^{\otimes n}(x^n,y^n)\indic{g_n(f_n(x^n),y^n)\neq x^n}. \end{align*}\]

Source coding with side information

  • Define again \[ C_{\textsf{source}}\eqdef \inf\left\{R: \exists {(f_n,g_n)}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=0\right\} \]

For a discrete memoryless source \(P_{XY}\), \(C_{\textsf{source}} = \bbH(X|Y)\)

  • This should be suprising: the decoder does not know \(y^n\)

Consider a sequence of \((n,M_n)\) codes \(\set{(f_n,g_n)}_{n\geq1}\) such that \[ \lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=0 \] Then \(R\geq \bbH(X|Y)\).

Achievability - One Shot Lemma

  • The achievability uses again random binning

  • Consider a source \(P_{UV}\), assume \(P_{U|V}(u,v)>0\) for all \((u,v)\) and set \(n=1\) for simplicity

  • Define the set \[ \calB_\gamma\eqdef\left\{(u,v)\in\calU\times\calV:\log\frac{1}{P_{U|V}(u|v)}\leq\gamma\right\}. \]

  • Encoding function \(f:\calU\to \set{1;M}\) created by assigning an index uniformly at random in \(\set{1;M}\) to each \(u\in\calU\)

  • Decoding function \(g:\intseq{1}{M}\times\calV:(m,v)\mapsto u^*\), where \(u^*=u\) if \(u\) is the unique sequence such that \((u,v)\in\calB_\gamma\) and \(f(u)=w\); otherwise, a random \(u\) is declared

On average (over the random binning to create \(F\)), \[ \E[C]{P_e} \leq \P[P_{U}]{U\notin \calB_\gamma} + \frac{2^{\min(\gamma,\log_2\abs{\calU})}}{M}. \]

Privacy amplification

Image
Privacy amplification model

A \((n,K_n)\) code \(\calC\) for privacy amplification coding a discrete memoryless source \(p_X\) against side information \(Z\) consists of an encoding function \(f_n:\calX^n\to\set{1;K_n}\).

  • The performance of an \((n,K_n)\) code is measured in terms of

    1. The rate of the code \(R\eqdef \frac{\log_2 K_n}{n}\) (bits/source symbol)

    2. The secrecy and uniformity of \(M\) measured as

      \[\begin{align*} S^{(n)}(\calC) \eqdef \bbV(p_{MZ^n},q_Mp_Z^{\otimes n}) \end{align*}\]

      where \(q_M\) is the uniform distribution on \(\set{1;K_n}\)

Privacy amplification

  • Define again \[ C_{\textsf{pa}}\eqdef \inf\left\{R: \exists \set{f_n}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log K_n}{n}\geq R \text{ and } \lim_{n\to\infty}S^{(n)}=0\right\} \]

For a discrete memoryless source \(P_{XZ}\), \(C_{\textsf{pa}} = \bbH(X|Z)\)